package com.yifan.sortAlgorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author YIFan
 * @Date 2020/6/12 17:22
 * @Version 1.0
 */
// 排序算法
public class SortAlgorithm {
    public static void main(String[] args) {
        int[] arr = {3, 6, 4, 2, 1, 9, 8, 5, 7};
        System.out.println("原数组->"+Arrays.toString(arr));
//        System.out.println("冒泡排序->"+Arrays.toString(bubbleSort(arr)));
        System.out.println("快速排序->"+Arrays.toString(quickSort(arr,0,arr.length-1)));
        System.out.println("插入排序->"+Arrays.toString(insertSort(arr)));
//        System.out.println("希尔排序->"+Arrays.toString(ShellSort(arr)));
    }

    // 冒泡排序
    /**
     *  arr = {3, 6, 4, 2, 1, 9, 8, 5, 7}  共需要比较 length-1 轮
     *  3, 6, 4, 2, 1, 9, 8, 5, 7    第一次比 3 - 6
     *  3, 4, 6, 2, 1, 9, 8, 5, 7    第二次比 4 - 6
     *  3, 4, 2, 6, 1, 9, 8, 5, 7    第二次比 6 - 2
     *  3, 4, 2, 1, 6, 9, 8, 5, 7    第二次比 6 - 1
     *  ......
     *  3, 4, 2, 1, 6, 8, 5, 7, 9    第一轮结束
     *
     * */
    public static int[] bubbleSort(int[] arr){

        // 控制比较多少轮
        for (int i = 0; i < arr.length - 1; i++) {
            // 控制比较的次数
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

    // 快速排序  {3, 6, 4, 2, 1, 9, 8, 5, 7};
    public static int[] quickSort(int[] arr,int start,int end){
        if (start<end){
            // 把数组中第一个数字作为标准数
            int stard = arr[start];
            // 记录需要排序的坐标  low high 指下标
            int low = start;
            int high = end;
            // 循环找比标准数大的数和比标准数小的数
            while (low < high){
                // 右边的数比标准的数大,数字不需要移动位置 ,下标前移
                while (low<high && stard<arr[high]){
                    high--;
                }
                // 右边的数比标准的数小,则把这个数替换左边下标的数
                arr[low] = arr[high];

                // 如果左边的数比标准数小则左边的下标后移
                while (low<high && stard>=arr[low]){
                    low++;
                }
                // 左边的数比标准数大 则把左边这个数和右边下标的数替换
                arr[high] = arr[low];

            }
            // 把标准数赋给左边下标元素所在位置
            arr[low] = stard;
            // 处理所有比标准数小的数
            quickSort(arr,start,low);
            // 处理所有比标准数大的数
            quickSort(arr,low+1,end);

            return arr;
        }
       return null;
        
    }

    // 直接插入排序
    /**
    * 比如  arr = { 2, 3, 4, 1, 0}
    *  temp = 1  i = 3
    *
    *  j = 2
    *  arr[j+1] 就为 temp的值 1
    *  arr[j] 就为 4
    *  把 1 变为 4
    *  arr = { 2, 3, 4, 4, 0}
    *
    *  j = 1
    *  arr[j+1] 就为 4
    *  arr[j] 就为 3
    *  把 4 变为 3
    *  arr = { 2, 3, 3, 4, 0}
    *
    *  j = 0
    *  arr[j+1] = 3
    *  arr[j] = 2
    *  把 3 变为 2
    *  arr = { 2, 2, 3, 4, 0}
    *
    *  j = -1
    *  j的循环条件不满足跳出
    *  arr[j+1] 为 1
    *  arr = { 1, 2, 3, 4, 0}
    *
    *  temp = 0 i = 4
    *  j = 3
    *  ...如上执行
    *  arr = { 0, 1, 2, 3, 4}
    *
    * */
    public static int[] insertSort(int[] arr){
        // 遍历所有的数字
        for (int i = 1; i < arr.length; i++) {
            // 当前的数比前一个数小
            if (arr[i] < arr[i-1]){
                // 把当前遍历的数存起来
                int temp = arr[i];
                // 遍历当前数字前面的所有数字 从后往前遍历
                int j;
                for ( j = i-1; j >= 0 && arr[j] > temp; j--) {
                    // 需要把数组里的第j个元素赋值给第j+1个元素
                    arr[j+1] = arr[j];
                }
                arr[j+1] = temp;
            }

        }
        return arr;
    }

    // 希尔排序
    public static int[] ShellSort(int[] arr){
        // 遍历所有的增量-开始为数组长度的一半
        for (int group = arr.length/2 ; group > 0 ; group /= 2){
            //对各个分组进行排序
            for (int i=group;i<arr.length;i++){
                //遍历本组中所有的元素
                for (int j = i-group; j>=0 ;j = j-group){
                       if (arr[j] > arr[j+group]){
                           int temp = arr[j];
                           arr[j] = arr[j+group];
                           arr[j+group] = temp;
                       }
                }
            }

        }
        return arr;
    }




}
